The present invention is directed generally to a system and method for solving packing and component layout problems, and more particularly to packing rectangular strips.
In manufacturing, it is frequently necessary to lay out patterns on a large piece of stock, and then to cut the stock into smaller pieces of various sizes to make a finished product. Typically, the component pieces must be located in such a manner that certain spatial constraints are satisfied. These spatial constraints often include orientation, proximity, and overlap. This is generally known as the xe2x80x9cpackingxe2x80x9d problem.
For example, an article of clothing is usually made from various irregularly shaped pieces cut from a bolt of fabric. Similarly, a piece of furniture may require specific rectangular pieces of glass or wood cut from a large sheet of glass or plywood. In all cases, it is desired to minimize both the amounts of stock and waste.
Although the two-dimensional (2D) rectangular strip packing problem is more constrained than the general case of irregular shaped pieces, it is still important to many engineering and manufacturing applications, see Coffman et al., xe2x80x9cApproximation algorithms for bin-packing: an updated survey,xe2x80x9d Algorithm Design for Computer Systems Design, Springer-Verlag, Ausiello et al. editors, pp. 49-106 1984, and Dyckhoff, xe2x80x9cTypology of cutting and packing problems,xe2x80x9d European Journal of Operational Research, 44, pp. 145-159, 1990.
When a computerized method is used to solve the 2D rectangular strip packing problem, the input is typically a permuted list of n input rectangles along with their dimensions, and a target width W. The object is to pack the n input rectangles, without overlap, into a single target rectangle of width W, and a minimum height H. A spatial constraint requires that all rectangles are placed orthogonally and parallel to the horizontal and vertical axes, i.e., the rectangles cannot be rotated, other than in 90xc2x0 steps. Like most packing problems, 2D rectangular strip packing, even with these spatial constraints, is NP-hard, because the number of different permutations that are possible is exponentially large in the number of rectangles.
One method for packing takes the list of input rectangles, and sorts them according to width or height, and greedily place the sorted rectangles, one by one, on the target rectangle. Perhaps, the most studied and effective heuristic, with the above constraints, is the bottom-left (BL) heuristic, where rectangles are placed sequentially, first as close to the bottom as possible, and then as far to the left as the rectangles can fit.
However, for some problems, the BL heuristic cannot find the optimal packing, nor does it perform well when applied to random instead of sorted orderings, see Baker et al., xe2x80x9cOrthogonal packings in two dimensions,xe2x80x9d SIAM Journal on Computing, 9:846-855, 1980, and Brown, xe2x80x9cAn improved BL lower bound,xe2x80x9d Information Processing Letters, 11:37-39, 1980.
However, a very successful approach applies the BL method to permutations of rectangles that are ordered by decreasing height, width, perimeter, and area, and returns the best of the four packings that result see Hopper, xe2x80x9cTwo-Dimensional Packing Utilising Evolutionary Algorithms and other Meta-Heuristic Methods,xe2x80x9d Ph.D. Thesis, Cardiff University, UK, 2000. That method is referred to as bottom-left-decreasing (BLD).
A natural alternative approach would find good orderings of the rectangles for BL or other similar heuristics, using standard search techniques such as simulated annealing, genetic algorithms, or tabu search. However, despite significant efforts in this area, the large search space has not proven amenable to such search techniques, see Hopper et al., xe2x80x9cAn Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem,xe2x80x9d European Journal of Operational Research, 128(1):34-57, 2000.
Another approach uses an approximation procedure. The BL heuristic has been shown to be a 3-approximation when the rectangles are sorted by decreasing width. However, that approach is not competitive when sorted by decreasing height. Other approaches give an asymptotic 5/4-approximation, see Baker et al., xe2x80x9cA 5/4 algorithm for two-dimensional packing,xe2x80x9d Journal of Algorithms, 2:348-368, 1981, and an absolute 5/2-approximation, see Sleator, xe2x80x9cA 2.5 times optimal algorithm for packing in two dimensions,xe2x80x9d Information Processing Letters, 10:37-40, 1980. A fully polynomial approximation scheme has also been described, see Kenyon et al., xe2x80x9cApproximate Strip-Packing,xe2x80x9d Proceedings of the 37th Annual Symposium on Foundations of Computer Science,xe2x80x9d pp. 31-36, 1996.
For many practical applications, humans usually outperform the best computerized methods, particularly for irregular shapes. Because humans still appear to be able to do better than automated methods, it is desired to provide an interactive system and method where the user can improve upon solutions provided by a computerized method.
The invention provides a method for optimally packing input rectangles into a target rectangle. The method can be used in a divide-and-conquer process for packing problems with a large number of rectangles. In addition, an interactive interface can be used to improve upon computer generated solutions.
A method packs input rectangles into a target rectangle. The rectangles are permuted into one or more an ordered list according to dimensions of the rectangles, e.g., width, height, perimeter, and area.
The rectangles are then marked as unaccepted. A next unaccepted rectangle is selected from the ordered list beginning with a first rectangle in the list. Accepting the next rectangle if it is the last unaccepted rectangles.
Otherwise, accepting the next rectangle with a probability p, and marking the next rectangle as accepted, and repeating the steps until all rectangles have been accepted.